from enum import Enum


# 导入枚举类
# 枚举类---红黑树
class Color(Enum):
    BLACK = 0
    RED = 1


class RedBlackTree():
    class Node:
        def __init__(self, key, value, left=None, right=None, color=Color.RED, p=None):
            self.key = key
            self.value = value
            self.left = left
            self.right = right
            self.p = p
            self.color = color

    def __init__(self):
        self.NIL = RedBlackTree.Node(None, None)
        self.NIL.right = self.NIL
        self.NIL.left = self.NIL
        self.NIL.p = self.NIL
        self.NIL.color = Color.BLACK
        self.root = self.NIL
        self.size = 0

    def search(self, key):
        cur = self.root
        while cur is not self.NIL:
            if cur.key == key:
                return cur.value
            elif cur.key > key:
                cur = cur.left
            else:  # cur.key < key
                cur = cur.right
        return None

    def __search(self, key):
        cur = self.root
        while cur is not self.NIL:
            if cur.key == key:
                return cur
            elif cur.key > key:
                cur = cur.left
            else:  # cur.key < key
                cur = cur.right
        return None

    def left_rotate(self, node: Node):
        nodeR = node.right
        node.right = nodeR.left
        if nodeR.left is not self.NIL:
            nodeR.left.p = node
        nodeR.p = node.p
        if node.p is self.NIL:
            self.root = nodeR
        elif node is node.p.left:
            node.p.left = nodeR
        else:
            node.p.right = nodeR
        nodeR.left = node
        node.p = nodeR

    def right_rotate(self, node: Node):
        nodeL = node.left
        node.left = nodeL.right
        if nodeL.right is not self.NIL:
            nodeL.right.p = node
        nodeL.p = node.p
        if node.p is self.NIL:
            self.root = nodeL
        elif node is node.p.right:
            node.p.right = nodeL
        else:
            node.p.left = nodeL
        nodeL.right = node
        node.p = nodeL

    def insert(self, key, value):
        self._insert(self.Node(key, value, self.NIL, self.NIL))

    def _insert(self, node):
        p = self.NIL
        cur = self.root
        while cur is not self.NIL:
            p = cur
            if cur.key is node.key:
                cur.value = node.value
                return
            elif cur.key > node.key:
                cur = cur.left
            else:
                cur = cur.right
        node.p = p
        if p is self.NIL:
            self.root = node
        elif p.key < node.key:
            p.right = node
        else:
            p.left = node
        self.size += 1
        self._insert_fixup(node)

    def _insert_fixup(self, node):
        while node.p.color is Color.RED:
            grand = node.p.p
            if node.p is grand.left:
                uncle = grand.right
                if uncle.color is Color.RED:
                    node.p.color = Color.BLACK
                    uncle.color = Color.BLACK
                    node.p.color = Color.RED
                    node = grand
                # uncle.color is BLACK
                elif node is node.p.right:
                    node = node.p
                    self.left_rotate(node)
                grand = node.p.p
                grand.color = Color.RED
                node.p.color = Color.BLACK
                self.right_rotate(node)
            else:
                uncle = grand.left
                if uncle.color is Color.RED:
                    node.p.color = Color.BLACK
                    uncle.color = Color.BLACK
                    node.p.color = Color.RED
                elif node is node.p.left:
                    node = node.p
                    self.right_rotate(node)
                grand = node.p.p
                grand.color = Color.RED
                node.p.color = Color.BLACK
                self.left_rotate(node)
        self.root.color = Color.BLACK

    def delete(self, key):
        node = self.__search(key)
        self.__delete(node)

    def _transplant(self, u,v):
        if u.p is self.NIL:
            self.root = v
        elif u == u.p.left:
            u.p.left = v
        else:
            u.p.right = v
        v.p = u.p

    def minimum(self, node: Node):
        if node is self.NIL:
            return None
        while node.left is not self.NIL:
            node = node.left
        return node
    def _delete(self, node):
        delete_node = node
        delete_node_origin_color = delete_node.color
        if node.left is self.NIL:
            



